package class19;

/**
 * @author YZY
 * @since 2022/8/18 17:28
 * 规定1和A对应、2和B对应、3和C对应...26和Z对应
 * 那么一个数字字符串比如"111”就可以转化为:
 * "AAA"、"KA"和"AK"
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
 */
public class Code02_ConvertToLetterString {

    // 暴力递归
    public static int convertToLetterString1(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process1(str.toCharArray(), 0);
    }

    private static int process1(char[] str, int index) {
        if (index == str.length) {
            return 1;
        }
        if (str[index] == '0') {
            return 0;
        }
        int ways = process1(str, index + 1);
        if (index + 1 < str.length && (str[index] - '0') * 10 + str[index + 1] - '0' < 27) {
            ways += process1(str, index + 2);
        }
        return ways;
    }

    // 记忆化搜索
    public static int convertToLetterString2(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int[] dp = new int[str.length()];
        return process2(str.toCharArray(), dp, 0);
    }

    private static int process2(char[] str, int[] dp, int index) {
        if (index == str.length) {
            return 1;
        }
        if (dp[index] != 0) {
            return dp[index];
        }
        if (str[index] == '0') {
            return 0;
        }
        int ways = process2(str, dp, index + 1);
        if (index + 1 < str.length && (str[index] - '0') * 10 + str[index + 1] - '0' < 27) {
            ways += process2(str, dp, index + 2);
        }
        return dp[index] = ways;
    }

    // 动态规划
    public static int convertToLetterString3(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            if (str[i] == '0') {
                continue;
            }
            int ways = dp[i + 1];
            if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
                ways += dp[i + 2];
            }
            dp[i] = ways;
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(convertToLetterString1("7210231231232031203123"));
        System.out.println(convertToLetterString2("7210231231232031203123"));
        System.out.println(convertToLetterString3("7210231231232031203123"));
    }

}
